/*
 * @Author: 缄默
 * @Date: 2021-12-11 20:38:54
 * @LastEditors: 缄默
 * @LastEditTime: 2021-12-12 21:43:55
 */

//最小编辑代价

//动态规划必须先找到变量之间变化的关系，根据之前的数据求得之后得要找到动态转移方程，在根据动态转移方程求出dp表，然后求出所需要的值
#include <iostream>
#include <vector>
#include <string>
#include <math.h>

using namespace std;

int minCost1(string s1, string s2, int ic, int dc, int rc);

int main() {
    string s1 = "ad";
    string s2 = "adc";
    const int ic = 5;
    const int dc = 3;
    const int rc = 2;

    cout << minCost1(s1, s2, ic, dc, rc) << endl;

    return 0;
}

int minCost1(string s1, string s2, int ic, int dc, int rc) {
    if (s1.size() == 0 || s2.size() == 0) return 0;

    int row = s1.size() + 1;
    int col = s2.size() + 1;
    vector<vector<int>> dp(row, vector<int>(col));
    for (int i = 1; i < row; i++) {
        //全部元素都要删除才能等于0
        dp[i][0] = dc * i;
    }
    for (int j = 1; j < col; j++) {
        //全部元素增加才可相等
        dp[0][j] = ic * j;
    }
    //列出dp数组得解法，即动态转移方程
    //开始根据动态方程求解dp数组
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            if (s1[i] == s2[j]) {
                dp[i][j] = min(dp[i - 1][j] + dc, dp[i][j - 1] + ic);
                dp[i][j] = min(dp[i - 1][j - 1], dp[i][j]);
            }
            else {
                dp[i][j] = min(dp[i - 1][j] + dc, dp[i][j - 1] + ic);
                dp[i][j] = min(dp[i - 1][j - 1] + rc, dp[i][j]);
            }
        }
    }
    return dp[row - 1][col - 1];
}


